package 滑动窗口And双指针;

import java.util.*;

public class SlideWindow {
	/*
	窗口中最大（最小值的更新结构）
	给你一个 w （窗口的大小） 和一个 数组 arr
	从 left 遍历 arr 每次 划过 一个 w 窗口
	返回 每次窗口中的最大值
	 */
		public static int[] getMaxWindow(int[] arr, int w) {
			if (arr == null || w < 1 || arr.length < w) {
				return null;
			}
			LinkedList<Integer> qmax = new LinkedList<Integer>();
			int[] res = new int[arr.length - w + 1];
			int index = 0;
			for (int i = 0; i < arr.length; i++) {
				while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {
					qmax.pollLast();
				}
				qmax.addLast(i);
				if (qmax.peekFirst() == i - w) {
					qmax.pollFirst();
				}
				if (i >= w - 1) {
					res[index++] = arr[qmax.peekFirst()];
				}
			}
			return res;
		}




		/*
		暴力解
		 */
		public static int [] violent(int arr[],int w){
			int len =  arr.length;
			// 结束的 时候 会 产生 len - w + 1 个值
			int ans [] = new int[len - w + 1];
			// 记录收集元素的 索引 下标
			int index = 0;
			for(int i = 0;i + w - 1 < len;i++){
				int max = Integer.MIN_VALUE;
				for(int j = i;j < i+ w;j++){
					max = Math.max(max,arr[j]);
				}
				ans[index++] = max;
 			}
			return ans;
		}


		/*
		 在实现 一遍这个结构
		 */
		public static int [] realize(int arr[],int w){
			int len = arr.length;
			int ans [] = new int[len - w + 1];
			int index = 0;
			// 采用这种 队列吧
			/*
			一定要注意一点 就是 ，这里的 queue 存储的 是元素的  index 索引下标，这里 在获取的 元素的
			全部都是下标，这里很容易出错！
			 */
			Deque<Integer> queue = new ArrayDeque<>();
			for(int i = 0;i < len ; i++){
				while(!queue.isEmpty() && arr[queue.peekLast()] <= arr[i]){
					queue.pollLast();
				}
				queue.addLast(i);
				//  窗口向右 滑动的过程中 ，如果当前队列的 最右边的 值 是要 出 窗口的 那就直接出去, 已经出去的话，就不管了
				if(i - w == queue.peekFirst())
					queue.pollFirst();
				// 表示形成了 一个窗口 ，开始收集结果
				if(i - w + 1 >= 0)
					ans[index++] = arr[queue.peekFirst()];
			}
			return ans;
		}











		public static void main(String[] args) {
			int[] arr = { 4, 3, 5, 4, 3, 3, 6, 7 };
			int w = 3;
			System.out.println(Arrays.toString(getMaxWindow(arr, w)));
			System.out.println(Arrays.toString(violent(arr,w)));
			System.out.println(Arrays.toString(realize(arr,w)));
		}
}
